package Demo1_12;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-01-12
 * Time:22:21
 */
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

// 实现链表划分功能的类
class PartitionList {
    public ListNode partition(ListNode pHead, int x) {
        // 存放小于x的节点的链表头
        ListNode lessHead = new ListNode(0);
        ListNode lessTail = lessHead;
        // 存放大于等于x的节点的链表头
        ListNode greaterHead = new ListNode(0);
        ListNode greaterTail = greaterHead;

        // 遍历原链表
        while (pHead!= null) {
            if (pHead.val < x) {
                lessTail.next = pHead;
                lessTail = lessTail.next;
            } else {
                greaterTail.next = pHead;
                greaterTail = greaterTail.next;
            }
            pHead = pHead.next;
        }

        // 处理边界情况，防止出现循环链表
        greaterTail.next = null;

        // 将两个链表连接起来
        lessTail.next = greaterHead.next;

        return lessHead.next;
    }


// 测试类
    public static void main(String[] args) {
        // 构建测试链表
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(2);

        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        PartitionList partitionList = new PartitionList();
        ListNode result = partitionList.partition(head, 3);

        // 输出重新排列后的链表
        while (result!= null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

